Salem Methodist Church originated as a unofficial Methodist sermon group in 1850, utilizing a simple log cabin as its place of worship, led by J.B. Dobbs. At the time of its formation, the Methodist Church has split in two, based on principles of slavery: the "Methodist Episcopal Church" supporting abolition (with several of its churches being active in the Underground Railroad); and "Methodist Episcopal Church, South" removing abolitionist teachings from its sermons in order to maintain its southern congregation. Being in Alabama, this church being of the latter.

It wasn't until 1865 that it became official, with a brand new small frame building next to the log cabin to function as both a house of worship and school building. The land it was built on was deeded from G.W. and Jane Black to William A. Elrod, Aaron N. Lowrey, William Nunn, and Nelson Elrod. Philip Elrod would preach the first sermon, as well as be the first person buried in the cemetery in 1872 (Contested! The first headstone to be erected in the cemetery was for his relation Adam S. Elrod, killed in 1863 while fighting for the Confederacy in central Tennessee. It is unknown if the body was recovered and buried there). Aaron N. Lowrey would be its first recorded pastor.

In 1890, the church was consecrated; in 1920, an addition housing 4 Sunday School rooms was added. At some point after 1939, the church was rebuilt with brick and renamed the Salem Methodist United Church.

On December 10, 2022, the church was officially closed its doors.